import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: 最帅的的乐乐
 * @date: 2024-05-07 16:10 星期二
 * @motto the harder, the luckier。
 * 在这里输入d然后回车就可生成完成时间
 * Completed at @date: 2024-05-07 18:40
 *
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
 * 同时还满足 nums[i] + nums[j] + nums[k] == 0 。
 *
 * 请你返回所有和为 0 且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 */

public class _15_ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for(int k = 0; k < nums.length - 2; k++){
            if(nums[k] > 0) break;
            //以避免生成重复的组合
            if(k > 0 && nums[k] == nums[k - 1]) continue;
            int i = k + 1, j = nums.length - 1;
            while(i < j){
                int sum = nums[k] + nums[i] + nums[j];
                if(sum < 0){
                    //这个 while 循环的主体是空的（即在循环体内没有任何代码），它只是利用循环条件来移动 i 指针，以跳过数组中的重复元素。
                    // 具体来说，这个循环通过增加 i 的值来跳过相同的元素，从而确保在接下来的逻辑中处理数组时，i 指向一个不同的值。
                    while(i < j && nums[i] == nums[++i]);
                } else if (sum > 0) {
                    while(i < j && nums[j] == nums[--j]);
                } else {
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
                    while(i < j && nums[i] == nums[++i]);
                    while(i < j && nums[j] == nums[--j]);
                }
            }
        }
        return res;
    }
    public static void main(String[] args) {
        _15_ThreeSum solution = new _15_ThreeSum();
        int[] nums = {-1, 0, 1, 2, -1, -4};
        List<List<Integer>> result = solution.threeSum(nums);
        for (List<Integer> list : result) {
            System.out.println(list);
        }
    }
}
